package 简单.栈;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
 * 商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与
 * prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 
 * 的 最小下标 ，如果没有满足条件的 j ，你将没有任何折扣。
 * 请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop
 */
public class 商品折扣后的最终价格_1475 {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(finalPrices2(new int[]{8, 4, 6, 2, 3})));

    }

    /**
     * 模拟
     *
     * @param prices
     * @return
     */
    public int[] finalPrices(int[] prices) {
        int[] ans = new int[prices.length];
        for (int i = 0; i < prices.length; i++) {
            ans[i] = prices[i];
            for (int j = i + 1; j < prices.length; j++) {
                if (prices[j] <= prices[i]) {
                    ans[i] -= prices[j];
                    break;
                }
            }
        }
        return ans;
    }

    /**
     * 单调栈+倒序遍历
     * [8,4,6,2,3]
     * 栈顶元素如果比入栈元素大，那么将栈顶元素弹出，
     * 直至栈为空，说明右边没有比入栈元素小的价格
     * 或者栈顶元素比入栈元素小，说明已经找到入栈元素右边第一个小于它价格的折扣
     * 将入栈元素入栈
     *
     * @param prices
     * @return
     */
    public static int[] finalPrices2(int[] prices) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] ans = new int[prices.length];
        int idx = prices.length - 1;
        while (idx >= 0) {
            ans[idx] = prices[idx];
            while (!stack.isEmpty() && stack.peekFirst() > prices[idx]) {
                stack.pollFirst();
            }
            if (!stack.isEmpty()) {
                ans[idx] -= stack.peekFirst();
            }
            stack.addFirst(prices[idx]);
            idx--;
        }
        return ans;
    }

}
